---
title: "最大数字"
created: 2025-11-28
tags:
  - 算法
---

# 最大数字

## 题目 [最大数字](https://www.lanqiao.cn/paper/3826/problem/2193/)

![[image-3d0249d5.png]]

## 思路分析

贪心吗

优先对高位进行操作 最高位达到9了再考虑第二位以此类推

貌似可行

第二个问题 对于4 能加4次 减5次 怎么选择 6 能加3次 减7次 怎么选择 有没有通用的公式 或者能不能直接枚举

而且还可以发现一个问题 对于某一位数 只会做一种操作 并不会搭配使用 因为是相消的

做第一种操作时（加） 要做9-x次才能到达9 如果到不了9 那就全给他让它尽可能大 即做A次 那么对于操作1 就是t=min(A,9-x)

做第二种操作（减） 只有变成0 再减1才会变成9 所以操作数应该是x+1次 如果到不了9 那干脆别做 只会越来越小 所以就是 能做就做x+1
不能做就不做

至于选了那种 就直接dfs 走不同的分支得到不同的结果 最后选择最大的

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
string s;
int A,B;
LL ans=0;

void dfs(int u,LL v){
	if(s[u]){
		int x=s[u]-'0';

		//第一种操作
		int op1=min(A,9-x);
		A-=op1;
		dfs(u+1,v*10+x+op1);
		A+=op1;

		//第二种操作
		if(B>x){
			B-=x+1;
			dfs(u+1,v*10+9);
			B+=x+1;
		}
	}
	else
		ans=max(ans,v);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>s>>A>>B;
	dfs(0,0);
	cout<<ans;
	return 0;
 }
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/04-冲刺国赛/国赛真题/第十三届蓝桥杯大赛软件赛决赛C-C++ 大学 B 组/卡牌|卡牌]] 🏠 [[00-冲刺国赛]] ➡️ [[出差|出差]]